package swardToOffer.struct_5_stack_or_queue;
// 面试题30：包含min函数的栈
// 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min
// 函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。

import java.util.Stack;

/**
 * 思路：辅助栈负责存储当前主栈中最小的元素于栈顶，
 * 如果当前压入主栈中的元素小于辅栈中栈顶元素，则同时压入，如果大于，则辅栈不压入
 * pop时需要弹出主栈的栈顶元素，若该元素与辅栈栈顶元素相等，则辅栈也弹出
 */

public class MinInStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    public MinInStack(){
        this.stack1=new Stack<>();
        this.stack2=new Stack<>();
    }
    public void push(Integer ele){
        if (stack2.isEmpty()||stack2.peek()>ele){
            stack2.push(ele);
        }
        this.stack1.push(ele);
    }
    public Integer pop(){
        if (stack1.isEmpty()) return null;
        Integer del = stack1.pop();
        if (del.equals(stack2.peek())) stack2.pop();
        return del;
    }

    public Integer min(){
        if (stack2.isEmpty()) return null;
        return stack2.peek();
    }

    public static void main(String[] args) {
        MinInStack Main = new MinInStack();
        Main.push(128);
        Main.push(200);
        Main.push(126);
        System.out.println(Main.min());
        System.out.println(Main.pop());
    }
}
